#include <rbtree.h>
#include <random.h>
#include <select.h>
#include <stdio.h>
#include <stdlib.h>
#define NUM 1000000
#define HASH 64
#define HMASK (HASH-1)
#define DEBUG

struct aa_node

{	struct rb_node rb;
	unsigned long num;
};


struct rb_node *find(struct rb_root *root,unsigned long offset)
{	struct rb_node *n=root->rb_node;
	unsigned long off;
	while (n)
	{
		off=(unsigned long)(((struct aa_node *)n)->num);

		if (off > offset)
			n = n->rb_left;
		else if (off < offset)
			n = n->rb_right;
		else{
			return  n;}
	}
	printf("never find %ld\n",offset);

	return NULL;
}


struct rb_node *insert(struct rb_root *root,unsigned long offset)
{	struct rb_node *n=root->rb_node,*parent=0;

	struct aa_node *a = malloc(sizeof(struct aa_node));
	if(!a)
		printf("no memory.\n");
	a->num=offset;
	a->rb.rb_parent=0;
	a->rb.rb_left=0;
	a->rb.rb_right=0;
	a->rb.level=1;
	unsigned long off=0;
	if(root->rb_node==0)
	{
		root->rb_node=&a->rb;
	return root->rb_node;
	}
 
	while (n)
	{
		off=(unsigned long)(((struct aa_node *)n)->num);
		if (off > offset){
			parent=n;
			n = n->rb_left;}
		else if (off < offset){
			parent=n;
			n = n->rb_right;}
		else
			return n;
		    
	}
	a->rb.rb_parent=parent;
	if(offset < off){
		parent->rb_left=&a->rb;
		rb_insert_color(parent->rb_left,root);}
	else{
		parent->rb_right=&a->rb;
		rb_insert_color(parent->rb_right,root);}
return n;

}

void delete(struct rb_root *root,unsigned long offset)
{	struct rb_node *node;
	node=find(root,offset);
	if(!node)
		printf("never delete %ld\n",offset);
	else
	{	rb_erase(node,root);
		free(node);
	}
}

main()
{	unsigned long i,r,s,j;
	unsigned long a[NUM];
	struct rb_root array[HASH];
#ifdef DEBUG
	int record[HASH];
#endif
	struct rb_root *root;
	for(i=0;i<HASH;i++)
	{array[i].rb_node=0;
#ifdef DEBUG
	record[i]=0;
#endif
	}
	struct rb_node *n;
	for(i=0;i<=20;i++){
		r=_random();
		j=r&HMASK;
	 	root=&array[j];
#ifdef DEBUG
		record[j]++;
#endif
		n=insert(root,r);
		a[i]=r;}
	while(i<NUM-1)
	{s=_select();
	 r=_random();
	 if(s==2)
	 {	j=r&HMASK;
	 	root=&array[j];
#ifdef DEBUG
		record[j]++;
#endif
	 	n=insert(root,r);
		a[i]=r;
		i++;
	 }
	 if(s==1)
	 {      r%=(i-2);
	 	j=a[r]&HMASK;
	 	root=&array[j];
	 	n=find(root,a[r]);
	 }
	 if(s==3)
	 {      i--;
	 	r=r%(i-2);
		j=a[r]&HMASK;
	 	root=&array[j];
#ifdef DEBUG
		record[j]--;
#endif
	 	delete(root,a[r]);
		a[r]=a[i];
		a[i]=0;
	}
	}
#ifdef DEBUG
	for(i=0;i<HASH;i++)
	{printf("The %ld hash tree has %d node.\n",i+1,record[i]);
	}
#endif
	exit(0);

}
